{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of People That Can Be Caught in Tag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: catchMaximumAmountofPeople"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #捉迷藏中可捕获的最大人数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你正在和你的朋友玩捉迷藏游戏。在捉迷藏比赛中，人们被分成两组：是 “鬼” 的人，和不是 “鬼” 的人。是 “鬼” 的人想要抓住尽可能多的不是 “鬼” 的人。</p>\n",
    "\n",
    "<p>给定一个 <strong>从 0 开始建立索引</strong> 的整数数组 <code>team</code>，其中只包含 0 (表示&nbsp;<strong>不是</strong> “鬼” 的人) 和 1 (表示是 “鬼” 的人)，以及一个整数 <code>dist</code>。索引 <code>i</code> 为 “鬼” 的人可以捕获索引在 <code>[i - dist, i + dist]</code>(<strong>包括</strong>) 范围内且 <strong>不是</strong> “鬼” 的任何<strong>一个</strong>人。</p>\n",
    "\n",
    "<p>返回 <em>“鬼” 所能捕获的最大人数</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> team = [0,1,0,1,0], dist = 3\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "在索引 1 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [1-3, 1+3] = [-2, 4] 内的人。\n",
    "他们可以抓住索引 2 中不是 “鬼” 的人。\n",
    "在索引 3 的 “鬼” 可以捕获范围 [i-dist, i+dist] = [3-3, 3+3] = [0, 6] 内的人。\n",
    "他们可以抓住索引 0 中不是 “鬼” 的人。\n",
    "在索引 4 上不是 “鬼” 的人不会被抓住，因为在索引 1 和 3 上的人已经抓住了一个人。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> team = [1], dist = 1\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "没有 “鬼\" 要抓的人。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> team = [0], dist = 1\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:\n",
    "</strong>没有 “鬼” 来抓人。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= team.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= team[i] &lt;= 1</code></li>\n",
    "\t<li><code>1 &lt;= dist &lt;= team.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-people-that-can-be-caught-in-tag](https://leetcode.cn/problems/maximum-number-of-people-that-can-be-caught-in-tag/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-people-that-can-be-caught-in-tag](https://leetcode.cn/problems/maximum-number-of-people-that-can-be-caught-in-tag/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,0,1,0]\\n3', '[1]\\n1', '[0]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 双指针\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        n = len(team)\n",
    "        j = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if team[i] == 1:\n",
    "                while j < n and (team[j] == 1 or j < i - dist):\n",
    "                    j += 1\n",
    "                    \n",
    "                if j < n and team[j] == 0 and i - dist <= j <= i + dist:\n",
    "                    ans += 1\n",
    "                    j += 1\n",
    "\n",
    "                if j == n:\n",
    "                    break\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        result = 0\n",
    "        visited = team[:]\n",
    "        l = 0\n",
    "        for i in range(len(team)):\n",
    "            if team[i] == 1:\n",
    "                left = max(0, i - dist)\n",
    "                right = min(i+dist, len(team) - 1)\n",
    "                l = max(l, left)\n",
    "                while l <= right:\n",
    "                    if team[l] == 0:\n",
    "                        result += 1\n",
    "                        l += 1\n",
    "                        break\n",
    "                    l += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        l=0\n",
    "        n=len(team)\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            if team[i]!=1:continue\n",
    "            l=max(l,i-dist)\n",
    "            while l<=min(n-1,i+dist):\n",
    "                if team[l]==0:\n",
    "                    res+=1\n",
    "                    l+=1\n",
    "                    break\n",
    "                l+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        n = len(team)\n",
    "        j = ans = 0\n",
    "        for i, x in enumerate(team):\n",
    "            if x == 1:\n",
    "                j = max(j, i - dist)\n",
    "                while j < n and team[j]:\n",
    "                    j += 1\n",
    "                if j < n and team[j] == 0 and j <= i + dist:\n",
    "                    ans += 1\n",
    "                    j += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        queue = deque()\n",
    "        ans = 0\n",
    "        n = len(team)\n",
    "        for i in range(n):\n",
    "            if team[i] == 0:\n",
    "                queue.append(i)\n",
    "        for i in range(n):\n",
    "            if team[i]:\n",
    "                while queue and queue[0] < i - dist:\n",
    "                    queue.popleft()\n",
    "                if queue and queue[0] <= i + dist:\n",
    "                    queue.popleft()\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        d = deque([i for i in range(len(team)) if team[i] == 0])\n",
    "        res = 0\n",
    "        for i in [i for i in range(len(team)) if team[i] == 1]:\n",
    "            while d and d[0]+dist < i:\n",
    "                d.popleft()\n",
    "            if d and abs(d[0]-i) <= dist:\n",
    "                d.popleft()\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        q=deque()\n",
    "        ans=0\n",
    "        for i,k in enumerate(team):\n",
    "            if k==0:\n",
    "                q.appendleft(i)\n",
    "        for i,k in enumerate(team):\n",
    "            if k==1:\n",
    "                while q and q[-1]+dist<i:\n",
    "                    q.pop()\n",
    "                if q and (q[-1]+dist<=i or q[-1]<=i+dist):\n",
    "                    q.pop()\n",
    "                    ans+=1\n",
    "                    continue\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        queue = deque()\n",
    "        for i,j in enumerate(team):\n",
    "            if j == 0:\n",
    "                queue.append(i)\n",
    "        ans = 0\n",
    "        for i,j in enumerate(team):\n",
    "            if j:\n",
    "                # 剔除掉不符合要求的索引\n",
    "                while queue and queue[0] < i-dist:\n",
    "                    queue.popleft()\n",
    "                #检查队列中是否有可以抓到的‘人’\n",
    "                if queue and queue[0]<=dist+i:\n",
    "                    queue.popleft()\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        queue = deque()\n",
    "        for i,j in enumerate(team):\n",
    "            if j == 0:\n",
    "                queue.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i,j in enumerate(team):\n",
    "            if j:\n",
    "                # 剔除掉不符合要求的索引\n",
    "                while queue and queue[0] < i-dist:\n",
    "                    queue.popleft()\n",
    "\n",
    "                #检查队列中是否有可以抓到的‘人’\n",
    "                if queue and queue[0]<=dist+i:\n",
    "                    queue.popleft()\n",
    "                    ans += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        queue = deque()\n",
    "        for i,j in enumerate(team):\n",
    "            if j == 0:\n",
    "                queue.append(i)\n",
    "        ans = 0\n",
    "        for i,j in enumerate(team):\n",
    "            if j:\n",
    "                # 剔除掉不符合要求的索引\n",
    "                while queue and queue[0] < i-dist:\n",
    "                    queue.popleft()\n",
    "                #检查队列中是否有可以抓到的‘人’\n",
    "                if queue and queue[0]<=dist+i:\n",
    "                    queue.popleft()\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        z, o = deque(),deque()\n",
    "        for i, t in enumerate(team):\n",
    "            if t == 0:\n",
    "                z.append(i)\n",
    "            else:\n",
    "                o.append(i)\n",
    "        res = 0\n",
    "        while z and o:\n",
    "            if z[0] - o[0] > dist:\n",
    "                o.popleft()\n",
    "            elif o[0] - z[0] > dist:\n",
    "                z.popleft()\n",
    "            else:\n",
    "                res += 1\n",
    "                o.popleft()\n",
    "                z.popleft()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        n = len(team)\n",
    "        lm = [0] * n\n",
    "        lg = [0] * n\n",
    "        im1 = ig1 = im2 = ig2 = 0\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if team[i] == 0: # man\n",
    "                b = 0\n",
    "                while ig1 < ig2: # 还有没抓到人的鬼，从左到右排列\n",
    "                    ig1 += 1\n",
    "                    idxg = lg[ig1 - 1]\n",
    "                    if idxg + dist >= i: # 鬼和当前人的距离是否超过dist\n",
    "                        b = 1\n",
    "                        break\n",
    "                if b == 1:\n",
    "                    ret += 1 # 人匹配到一个鬼\n",
    "                else:\n",
    "                    lm[im2] = i # 人没匹配到鬼，入列\n",
    "                    im2 += 1\n",
    "            else: # ghost\n",
    "                b = 0\n",
    "                while im1 < im2: # 还有没匹配到鬼的人，从左到右排列\n",
    "                    im1 += 1\n",
    "                    idxm = lm[im1 - 1]\n",
    "                    if idxm  + dist >= i: # 人和当前鬼的距离是否超过dist\n",
    "                        b = 1\n",
    "                        break\n",
    "                if b == 1: # 鬼匹配到一个人\n",
    "                    ret += 1\n",
    "                else:\n",
    "                    lg[ig2] = i # 鬼没匹配到人，入列\n",
    "                    ig2 += 1\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def catchMaximumAmountofPeople(self, team: List[int], dist: int) -> int:\n",
    "        n = len(team)\n",
    "        people, ghost = [], []\n",
    "        for i, j in enumerate(team):\n",
    "            if j:\n",
    "                ghost.append(i)\n",
    "            else:\n",
    "                people.append(i)\n",
    "        dq = deque(ghost)\n",
    "        ans = 0\n",
    "        for p in people:\n",
    "            if not dq:\n",
    "                break \n",
    "            while dq and p - dq[0] > dist:\n",
    "                dq.popleft()\n",
    "            if dq and abs(p - dq[0]) <= dist:\n",
    "                ans += 1\n",
    "                dq.popleft()\n",
    "            else:\n",
    "                continue\n",
    "        return ans "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
